Jogos
Exemplo (Cone Sul) Considere um tabuleiro m \times n . Em cada casa existe um inteiro não negativo assinalado. Uma operação consiste em escolher qualquer uma das duas casas com 1 lado em comum, e adicionar a estes 2 números o mesmo inteiro (ele pode ser negativo) de tal forma que os dois resultados sejam não negativos. Quais são as condições que devem ser satisfeitas inicialmente nos números assinalados das casos, de tal que forma que, depois de algumas operações, haverão 0 em todas as casas? Solução: Cada vez que somamos um inteiro em cada dos dois quadradinhos com lados em comum, alteramos o valor de uma casa na posição par e outra na posição ímpar. Podemos usar isto a nosso favor. Faremos o seguinte: pintaremos as casas do tabuleiro de preto e branco (conforme um tabuleiro de xadrez). Desta forma, podemos entender cada operação como sendo somar um inteiro k em uma casa de cada cor. Queremos saber se podemos fazer a soma dos números das casas brancas e das casas pretas seja igual a 0 . Se fizermos as operações de trás para frente, de uma rodada para a anterior devemos subtrair o mesmo inteiro k , tanto da soma dos números das casas brancas quanto a das somas pretas. Com isso, no início, a soma dos números das casas brancas é o mesmo das pretas. Resumo: já vimos que se pudermos zerar todas as casas, então a soma dos números das casas brancas é igual ao das casas pretas. Agora, se a soma das casas brancas for igual a soma das casas pretas, podemos zerar o tabuleiro? Sim! Como? Vamos imaginar que temos o tabuleiro com a soma dos números brancos igual à dos números pretos. Para zerar o tabuleiro, comecemos com o seguinte: vamos zerar subtrair números na coluna da direita até que todos eles zerem (observe que também mexeremos na coluna que fica à esquerda dela). Repita este processo até que sobre duas colunas. Faça o mesmo para as linhas até que sobre apenas uma só (sem ser zerada). Observe que sobrou um pedaço 2 \times 1 do tabuleiro. Um dos números estará em uma casa branca e o outro em uma casa preta. Como a soma da dos números casas brancas é igual à soma dos casas pretas, estes números são iguais. Logo, basta subtrairmos o mesmo número das duas casas para a zerarmos. Portanto, podemos zerar todas as casas se, e somente se, a soma dos números das casas brancas é igual ao das casas pretas. Exemplo (Cone Sul 1991) Duas pessoas, A e B , jogam o seguinte jogo: A começa escolhendo um número inteiro positivo e então, cada jogador em seu turno diz um número conforme as seguintes regras: Se o último número dito for ímpar, o jogador soma 7 a este número; Se o último número dito for par, o jogador divide ele por 2 . O ganhador é o jogador que repete o primeiro número dito. Encontre todos os números que A pode escolher para ganhar. Justifique sua resposta. Solução: O jogador A ganha se o número que ele escolheu na primeira vez aparecer em alguma posição ímpar (ou seja, ou na terceira, ou na quinta etc). Assim, os números que fazem A ganham aparecem de dois em dois. Se começarmos com um número "razoavelmente grande", ele diminui logo nas primeiras rodadas. Consideraremos aqui x o número inicial. Vamos encontrar algum valor para x suficientemente grande, tal que se x for maior que este número, ele irá diminuir a cada duas rodadas. Por que encontrar isto é bom? Porque saberemos que se o primeiro termo for maior que este número, então ele nunca poderá subir (se estivermos olhando a cada duas rodadas), isto é, ele nunca vai voltar ao número original. Como podemos olhar para as primeiras rodadas? Depende do valor de x . Existem três possibilidades: 1º Caso: x é ímpar. Aqui, os primeiros números serão x, x+7, \frac{x+7}{2} . Ele diminui a cada duas rodadas se, e somente se, x>\frac{x+7}{2} \Leftrightarrow x>7. 2º Caso: x é múltiplo de 4 . Aqui, os números que aparecerão depois de duas rodadas são x,\frac{x}{2}, \frac{x}{4} . Neste caso, x diminui a cada duas rodadas se, e somente se, x>\frac{x}{4} \Leftrightarrow x>0. 3º Caso: x é par, mas não é múltiplo de 4 . Os primeiros termos serão x,\frac{x}{2},\frac{x}{2}+7 . Aqui x diminuirá a cada duas rodadas se, e somente se, x>\frac{x}{2}+7 \Leftrightarrow x>14 Desta forma, em qualquer um dos casos, se x>14 , então ele nunca irá voltar ao número original nas posições ímpares. Por isso, devemos testar as soluções menores ou iguais a 14 . As únicas em que A ganha são 1, 2, 4, 7, 8, 14 . Exemplo (OBM 2004 - 3ª Fase - Nível 2) Esmeralda tem uma pilha com 100 pedras. Ela divide essa pilha em duas novas pilhas e em seguida multiplica as quantidades de pedras nessas duas novas pilhas e escreve o produto em um quadro. Ela então escolhe uma pilha com mais de uma pedra e repete esse procedimento: a pilha é dividida em duas , as quantidades de pedras nessas duas pilhas são multiplicadas e o produto escrito no quadro. Esta operação é realizada até se obter apenas pilhas com 1 pedra cada. Quais são os possíveis valores da soma de todos os produtos escritos no quadro? Solução: Faremos o seguinte: começaremos entendendo bem a conta depois de uma divisão qualquer em duas pilhas. Depois de entendida a álgebra desse processo, conseguiremos entender o processo de várias divisões com mais precisão nas contas. Considere uma pilha com a pedras que é distribuída em duas pilhas com Exemplo b e e pedras. O produto escrito no quadro será be . Podemos escrever este número de outra maneira? Vamos relacionar a , b e e de modo a aparecer esse produto. O que sabemos sobre eles? Primeiramente que a=b+e . E como fazer be aparecer? Uma maneira é elevarmos ambos os lados ao quadrado: a^2=b^2+2be+e^2 \Leftrightarrow be=\frac{a^2-b^2-e^2}{2} . Façamos o caso com várias divisões. Chamaremos de b_1 e b_2 as quantidades de pedras das pilhas depois da primeira divisão. As outras quantidades das próximas divisões serão b_3,b_4,\dots,b_i,b_{i+1} . Com isso, o número escrito no quadro será S=b_1b_2+b_3b_4+\dots+b_{i}b_{i+1}. Se aplicarmos o raciocínio que fizemos para a primeira pilha para todas essas divisões, teremos S=\frac{100^2-b_1^2-b_2^2}{2}+\frac{b_1^2-b_3^2-b_4^2}{2}+\dots+\frac{b_{i-1}^2-b_i^2-b_{i+1}^2}{2}. Observe que alguns b_t's se cancelam. Quais deles? Se b_t>1 , então \frac{b_x^2-b_t^2-b_y^2}{2} e \frac{b_t^2-b_x^2-b_w^2}{2} . Com isso, se b_t>1 , ele irá se cancelar. Mas se b_t=1 , ele não se cancelará. Observe que existirão 100 valores de t tais que b_t=1 . Desta forma, S=\frac{100^2-1-1-\dots-1}{2}=\frac{9900}{2}=4500 . Portanto, a única soma possível é 4500 . Pense de Trás Para Frente Exemplo (OBM 2004 - 3ª Fase - Nível 2) Em um jogo para dois participantes, Arnaldo e Bernaldo alternadamente escolhem um número inteiro positivo. A cada jogada, deve-se escolher um número maior que o último número escolhido e menor que o dobro do último número escolhido. Nesse jogo, vence o jogador que conseguir escolher o número 2004 . Arnaldo joga primeiro e inicia com o número 2 . Qual dos dois tem a estratégia vencedora, ou seja, consegue escolher o número 2004 independente das jogadas do adversário? Solução: Para nós, rodada será cada vez que uma pessoa joga. Chamemos de X a pessoa que escolheu o número 2004 e n a rodada em que essa pessoa faz isso. O outro jogador será chamado de Y . Vamos entender o que aconteceu nas rodadas n-1, n-2, \dots e assim por diante até conseguirmos descobrir qual foi a rodada inicial. Para que na rodada n , o jogador X tenha escolhido o número 2004 , o outro jogador deveria ter escolhido na rodada n-1 algum número entre 1003 e 2003 , (não dá para X ser menor que 1002 , pois aí X não poderia escolher o 1004 ). Outras Rodadas Anteriores Rodada Quem Escolhe Número Escolhido n-5 Y Entre 251 e 500 n-6 X Entre 251 e 500 n-7 Y Entre 251 e 500 n-8 X Entre 251 e 500 n-9 Y Entre 251 e 500 n-10 X Entre 251 e 500 n-11 Y Entre 251 e 500 n-12 X Entre 251 e 500 n-13 Y Entre 251 e 500 n-14 X Entre 251 e 500 n-15 Y Entre 251 e 500 n-16 X Entre 251 e 500 n-17 Y Entre 251 e 500 n-18 X Entre 251 e 500 n-19 Y Entre 251 e 500 Simetria Em certas ocasiões, se o jogador copiar a jogada do outro simetricamente, ele vence. Exemplo (OBM 2002 - 3ª Fase - Nível 2) São dados um tabuleiro quadriculado m\times n e palitinhos do tamanho dos lados das casas. Dois jogadores jogam alternadamente e, em cada jogada, um dos jogadores coloca um palitinho sobre um lado de uma casa do tabuleiro, sendo proibido sobrepor palitinhos. Vence o jogador que conseguir completar primeiro um quadrado 1\times 1 de palitinhos. Supondo que nenhum jogador cometa erros, qual dos dois jogadores tem a estratégia vencedora, ou seja, consegue vencer independentemente de como jogue seu adversário. Solução: Aqui a estratégia do espelhamento funciona. Mas temos que tomar cuidado com a paridade da quantidade de palitos que devem ser colocados. Se a quantidade palitos a serem colocadas for ímpar, existe um palito central. Caso contrário, a gente deve se basear no quadrado central. Vamos entender isso com mais calma. Em que casos a quantidade de palitos colocados será par? E em que casos será ímpar? Para sabermos isto, devemos nos perguntar: qual a quantidade de palitos que podemos colocar num tabuleiro m \times n ? Sem perda de generalidade, podemos supor que existem m quadradinhos na horizontal e n na vertical. Então será necessário colocar m(n+1) palitos na horizontal e n(m+1) na vertical. Com isso, precisaremos de m(n+1)+n(m+1)=2mn+m+n palitos. Vamos analisar a paridade desta última expressão. Como 2mn é par, segue que 2mn+m+n e m+n possuem mesma paridade (ao somarmos um número par a um número, não alteramos sua paridade). Desta forma, precisamos de uma quantidade ímpar de palitos se m e n tiverem mesma paridade, enquanto teremos uma quantidade par, caso contrário. Vejamos cada um dos casos. 1º Caso: A quantidade de palitos necessárias para cobrir o tabuleiro é ímpar. Neste caso, m e n possuem paridades diferentes. O primeiro jogador pode usar a técnica da simetria. Como? Basta ele começar colocando uma peça na posição central e "imitar" as jogadas do segundo, simetricamente com relação a esta peça do centro. Os jogadores sabem que quem colocar o terceiro palito em um quadrado 1\times 1 perde. Em alguma hora, todos os quadrados serão ocupados com dois palitos e será a vez do 2 º jogador. Ele vai ter que colocar o terceiro palito em algum dos quadradinhos e irá perder (pois o primeiro jogador irá completar o quadrado). Logo, nesta ocasião o primeiro jogador vence. 2º Caso: A quantidade de palitos necessárias para cobrir o tabuleiro é par. Neste caso, m e n possuem paridades iguais. Quem pode ter a estratégia vencedora é o segundo jogador: basta ele jogar espelhadamente em relação ao quadrado central. Quando tivermos todos os quadrados com 2 palitos, será a vez do primeiro jogador (que irá perder pelo mesmo raciocínio do caso anterior). Portanto, se m e n tem paridades diferentes, o primeiro jogador tem a estratégia vencedora. Caso contrário, quem consegue vencer é o segundo. Categoria:Matemática Categoria:Combinatória